package com.ssh;

import java.util.LinkedList;
import java.util.Queue;

import org.junit.Test;

public class MinPathLength {
	@Test
	public void test() {
		int[][] a = {{1,1,1,1},
		             {1,0,1,1},
		             {1,0,0,1},
		             {1,1,1,1}};
		System.out.println(minPathLength1(a, 2, 3));
	}
	public int minPathLength1(int[][] grids, int tr, int tc) {
		int[][] direct = {{-1,0},{1,0},{0,-1},{0,1}};
		int m = grids.length,n = grids[0].length;
		Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
		queue.add(new Pair(0,0));
		int len = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			len++;
			while (size-- > 0) {
				Pair<Integer, Integer> cur = queue.poll();
				for (int i = 0; i < 4; i++) {
					Pair<Integer, Integer> next = new Pair<Integer, Integer>(cur.getKey()+direct[i][0], cur.getValue()+direct[i][1]);
					if (next.getKey() < 0 || next.getKey() >= m || next.getValue() < 0 || next.getValue() >= n) {
						continue;
					}
					if (next.getKey() == tr && next.getValue() == tc) {
						return len;
					}
					if (grids[next.getKey()][next.getValue()] == 0) {
						continue;
					}
					grids[next.getKey()][next.getValue()] = 0;
					queue.add(next);
				}
			}
		}
		return -1;
	}
	
	public int minPathLength(int[][] grids, int tr, int tc) {
	    final int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	    final int m = grids.length, n = grids[0].length;
	    Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
	    queue.add(new Pair(0, 0));
	    int pathLength = 0;
	    while (!queue.isEmpty()) {
	        int size = queue.size();
	        pathLength++;
	        while (size-- > 0) {
	            Pair<Integer, Integer> cur = queue.poll();
	            for (int[] d : direction) {
	                Pair<Integer, Integer> next = new Pair(cur.getKey() + d[0], cur.getValue() + d[1]);
	                if (next.getKey() < 0 || next.getKey() >= m || next.getValue() < 0 || next.getValue() >= n)
	                    continue;
	                if (next.getKey() == tr && next.getValue() == tc)
	                    return pathLength;
	                if (grids[next.getKey()][next.getValue()] == 0) {
	                    continue;
	                }
	                grids[next.getKey()][next.getValue()] = 0; // 标记
	                queue.add(next);
	            }
	        }
	    }
	    return -1;
	}
	class Pair<T1, T2> {
		private T1 key;
		private T2 value;
		Pair(T1 key, T2 value) {
			this.key = key;
			this.value = value;
		}
		public T1 getKey() {
			return this.key;
		}
		public T2 getValue() {
			return this.value;
		}
	}
}
